package main

import "fmt"

//dfs方法，用时超过19%，内存超过37%
func islandPerimeter(grid [][]int) int {
	p := 0
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[0]); j++ {
			if grid[i][j] == 1 {
				dfs(grid, i, j, &p)
				return p
			}
		}
	}
	return p
}

func isArea(grid [][]int, r, c int) bool {
	return r >= 0 && r < len(grid) && c >= 0 && c < len(grid[0])
}

func dfs(grid [][]int, r, c int, p *int) {
	if !isArea(grid, r, c) {
		*p++
		return
	}
	if grid[r][c] == 0 {
		*p++
		return
	} else if grid[r][c] == 1 {
		grid[r][c] = 2
	} else {
		return
	}
	dfs(grid, r+1, c, p)
	dfs(grid, r-1, c, p)
	dfs(grid, r, c+1, p)
	dfs(grid, r, c-1, p)

}

//遍历方法，用时超过58%，内存超过67%，j+1 < len(grid[0])
//j < len(grid[0])-1，用时37%，内存67%，和上面类似
func islandPerimeter1(grid [][]int) int {
	land, border := 0, 0
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[0]); j++ {
			if grid[i][j] == 1 {
				land++
				if j < len(grid[0])-1 && grid[i][j+1] == 1 {
					border++
				}
				if i < len(grid)-1 && grid[i+1][j] == 1 {
					border++
				}
			}

		}
	}
	return land*4 - 2*border
}

func main() {
	c := '2'
	fmt.Println(c)
	grid := [][]int{{0, 1, 1}, {0, 1, 1}}
	// for i := 0; i < len(grid); i++ {
	// 	for j := 0; j < len(grid[0]); j++ {
	// 		fmt.Printf("%c\n", grid[i][j])
	// 	}
	// }
	// fmt.Println(grid)
	fmt.Println(islandPerimeter1(grid))
	fmt.Println(islandPerimeter(grid))
}
